#阶乘n × (n -1) × (n - 2) × … × 1
def factorial(n):
    result = n
    for i in range(1, n):
        result *= i
    return result

#幂
def power(x, n):
    result = 1
    for i in range(n):
        result *= x
    return result
#result *= i是每次都和自己相乘，乘i次
#result *= x 是每次都和x相乘，乘i次

#二分查找算法
#本质 ①如果上限和下限相同，就说明它们都指向数字所在的位置，因此将这个数字返回。②否则，找出区间的中间位置（上限和下限的平均值），再确定数字在左半部分还是右半部分。然后在继续在数字所在的那部分中查找。
def search(sequence, number, lower=0, upper=5):#需要上限和下限设置一个值,如果不赋值(sequence, number, lower, upper)会报错——TypeError: search() missing 2 required positional arguments: 'lower' and 'upper'
    if lower == upper:
        assert number == sequence[upper] #假设（断言）找到的确实是要找的数字
        return upper
    else:
        middle = (lower + upper) // 2
        if number > sequence[middle]:
          return search(sequence, number, middle + 1, upper)
        else:
          return search(sequence, number, lower, middle)

# #二分查找算法——可将上限和下限设置为可选的，将第19行替换为
# def search(sequence, number, lower=0, upper=None):
#     if upper is None: upper = len(sequence) - 1
#检验一下二分查找算法
seq = [34, 67, 8, 123, 4, 100, 95]
seq.sort()
print(search(seq, 34))
print(search(seq, 100))